public class Test {
}
class Solution {
    //i:第i个台阶
    //dp[]:花多少钱
    //dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
    //dp[0] = 0
    //dp[1] = 0
    //dp[2] = Math.min(cost[1],cost[0])
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[2] = Math.min(cost[0],cost[1]);
        for(int i=3; i<n+1; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
}
class Solution1 {
    //[i][j]:坐标
    //dp : 路径数
    //dp[i][j] = dp[i-1][j] + dp[i][j-1];
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0){
                    dp[i][j] = 1;
                }else if(j==0){
                    dp[i][j] = 1;
                }else
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++){
            if(obstacleGrid[i][0] == 1)
                break;
            dp[i][0] = 1;
        }
        for(int j=0; j<n; j++){
            if(obstacleGrid[0][j] == 1)
                break;
            dp[0][j] = 1;
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}
class Solution2 {
    //i:n
    //dp[i]:能拆成的最大乘积
    //初始化：dp[2]=1
    //递推公式：dp[i] = max(dp[i-j]*j,j*(i-j))
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i=3; i<n+1; i++){
            for(int j=2; j<i/2+2; j++){
                dp[i] = Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
            }
        }
        return dp[n];
    }
}